package 中等.分组循环;

import java.util.Arrays;

/**
 * 给你一个网格图，由 n + 2 条 横线段 和 m + 2 条 竖线段 组成，一开始所有区域均为 1 x 1 的单元格。
 * 所有线段的编号从 1 开始。
 * 给你两个整数 n 和 m 。
 * 同时给你两个整数数组 hBars 和 vBars 。
 * hBars 包含区间 [2, n + 1] 内 互不相同 的横线段编号。
 * vBars 包含 [2, m + 1] 内 互不相同的 竖线段编号。
 * 如果满足以下条件之一，你可以 移除 两个数组中的部分线段：
 * 如果移除的是横线段，它必须是 hBars 中的值。
 * 如果移除的是竖线段，它必须是 vBars 中的值。
 * 请你返回移除一些线段后（可能不移除任何线段），剩余网格图中 最大正方形 空洞的面积，正方形空洞的意思是正方形 内部 不含有任何线段。
 *
 * @ https://leetcode.cn/problems/maximize-area-of-square-hole-in-grid/description/
 * @date 2024/07/26
 */
public class 最大化网格图中正方形空洞的面积_2943 {

    public static void main(String[] args) {


    }

    /**
     * 如果一个横线被移除后，那么所有的竖线都能和剩下的横线组成正方形，反之亦然
     * 那么问题分解成求 hBars 里面连续数字的最长宽度 和 vBars 里面连续数字的
     * 最长高度，取一个较小的作为正方形答案的边长
     */
    public int maximizeSquareHoleArea(int n, int m, int[] hBars, int[] vBars) {
        Arrays.sort(hBars);
        Arrays.sort(vBars);

        int maxH = getMaxLinkLen(hBars) + 1;
        int maxV = getMaxLinkLen(vBars) + 1;

        return Math.min(maxH, maxV) * Math.min(maxH, maxV);
    }

    private static int getMaxLinkLen(int[] bars) {
        int max = 1;
        int left = 0, right = 1;
        while (right < bars.length) {
            if (bars[right] - bars[right - 1] > 1) {
                left = right;
                right++;
                continue;
            }
            max = Math.max(max, right - left + 1);
            right++;
        }
        return max;
    }

}
